package algorithms.sort;

import algorithms.Util;

/**
 * 选择排序<br>
 * 升序<br>
 * n为数组长度，i为元素index(从0开始递增)<br>
 * 扫描数组n-i个元素，找到最小值，放入第i个元素（交换）；<br>
 * 时间复杂度O(n^2)
 * @author shaoyuxia
 *
 * @param <T>
 */
public class SelectSort<T extends Comparable<T>> implements ISort<T> {

	@Override
	public T[] sort(T[] a) {
		for (int i = 0; i < a.length; i++) {
			// 每次遍历把最小值选出来和第i个元素交换
			for (int j = i + 1; j < a.length; j++) {
				if (a[i].compareTo(a[j]) > 0) {
					Util.exchange(a, i, j);
				}
			}
		}
		return a;
	}

}
